package io.github.hadyang.leetcode.offer;

import java.util.ArrayList;
import org.junit.Test;

/** @author haoyang.shi */
public class FindContinuousSequence {

  @Test
  public void test() {
    System.out.println(FindContinuousSequence(1));
    System.out.println(FindContinuousSequence(100));
  }

  public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    if (sum == 1) {
      return res;
    }

    int start = 1, end = 2;
    int t = start + end;

    while (start < end) {
      if (t == sum) {
        ArrayList<Integer> ints = new ArrayList<>();
        for (int i = start; i <= end; i++) {
          ints.add(i);
        }
        res.add(ints);
        t -= start;
        start++;
      } else if (t > sum) {
        t -= start;
        start++;
      } else {
        if (end >= sum) break;

        end++;
        t += end;
      }
    }

    return res;
  }
}
